1. Field of the Invention
The present invention relates to a packet switching apparatus and method applied in a network system, and particularly to a switching apparatus and method with rate guarantees and without internal speedup, using bandwidth decomposition.
2. Description of the Related Art
FIG. 1 is a schematic diagram of a well-known 4xc3x974 input-buffered crossbar switch, wherein one end of the crossbar switch 11 includes a plurality of input ports, and each input port includes an input buffer 12. The input buffers 12 are used to store packets entering the input ports and prevent losing the packets due to business of the crossbar switch 11. Another end of the crossbar switch 11 is connected to a plurality of output ports. There is a controller (not shown) at the intersection of each column and each row of the crosscar switch 11 to control the direction of data flow. As shown in FIG. 1, for example, a connecting point 13 represents a corresponding controller at the on position, and the first input port is connected to the fourth output port, the second input port is connected to the second output port, the third input port is connected to the first output port, the fourth input port is connected to the third output port. If logic one represents the on connection and logic zero represents the off connection, a permutation matrix can be derived to represent the above connection pattern. If the cycle time in which a fixed number of packets are transfered by the crossbar switch 11 is divided into a plurality of time slots with a minimum of one package transferred between any input port and any output port only occurring in one time slot, then synchronization of package transference will be derived. It is a key point to find out what the connection patterns of the crossbar switch 11 are in each time slot.
Prior art uses internal speed up inside the crossbar switch 11 to reach 100% throughput. In other words, the speed of packet switching should be faster than the speed of packet transference, and the ratio of that is about 2 times or even more. Besides, the maximal matching between input packets and output port of the crossbar switch 11 should be determined within every time slot to output the greatest number of packets within every time slot. As described above, because a maximal matching algorithm is executed within every time slot, the speed of the crossbar switch 11 can not be increased to fit the application to current high speed networks.
Another kind of crossbar switch without internal speedup is disclosed by A. Hung, G. Kesidis and N. Mckeown, xe2x80x9cATM input-buffered switches with guaranteed-rate property,xe2x80x9d Proc. IEEE ISCC""98, Athens, pp. 331-335, 1998, which uses a weighted round robin algorithm to derive rate guarantees and 100% output utilization. The above-mentioned crossbar switch must define a frame length beforehand, and packs constant number of input packets inside the frame. When the frame size is too large, the packet delay will be increased and a lot of memory will be needed to store all the connection patterns during the cycle time of the crossbar switch. When the frame size is too small, the utilization of the bandwidth will be decreased.
As mentioned above, the crossbar switch applied in current network transmission does not completely satisfy the needs of the market.
Accordingly, an objective of the present invention is to resolve the drawbacks of needing internal speedup and low utilization of the crossbar switch as in the prior art. In order to accomplish the object, the present invention proposes a switching apparatus applied in packet switching of a network system using bandwidth decomposition. The present invention also proposes a scheduling algorithm applied in an input-buffered crossbar switch. The present invention has the following characteristics:
(1) it is not necessary to speed up inside the present switching apparatus using bandwidth decomposition;
(2) it is not necessary to determine a maximal matching between input packets and output ports within every time slot;
(3) it is not necessary to define a frame length;
(4) the switching apparatus using bandwidth decomposition according to the present invention can reach 100% utilization of output rate;
(5) the present switching apparatus using bandwidth decomposition can afford quality of service (QoS) in network transmission, such as packet delay, queue length of input buffers, etc;
(6) the present switching apparatus using bandwidth decomposition affords different service qualities for clients with different service grades;
(7) In practical application, the present switching apparatus using bandwidth decomposition can be implemented by hardware circuit, especially being formed by a single chip and embedding the chip on the motherboard of a switching machine, such as Hub, Switch, etc.
The present invention proposes a switching apparatus applied in packet switching of a network system using bandwidth decomposition. An element ri,j in the rate matrix R=(ri,j) represents the input rate assigned to the traffic from the i-th input port to the j-th output port of an input-buffered Nxc3x97N crossbar switch. The apparatus aspect of the present invention mainly comprises a rate-measuring mechanism, a plurality of input ports, a crossbar switch and a processing mechanism. The rate-measuring mechanism is used to dynamically measure the input rate of the present switching apparatus. The plurality of input ports, connected to said rate-measuring mechanism, include a plurality of storing devices for storing input packets. The crossbar switch, connected to said plurality of input ports, is used to transfer said plurality of input packets to the plurality of output ports of said switching apparatus using bandwidth decomposition. The processing mechanism, connected to said rate-measuring mechanism, is used to transform said rate matrix into connection patterns of said crossbar switch in each time slot of the cycle time.
The present invention regarding method mainly comprises the following steps: the step of using a von Neumann algorithm to transform the rate matrix R= of a Nxc3x97N input-buffered crossbar switch to a doubly stochastic matrix {tilde over (R)}; the step of using a Birkhoff theorem to decompose said doubly stochastic matrix into a linear combination of a plurality of permutation matrices, all said plurality of permutation matrices corresponding to a connection pattern of said crossbar switch; and the step of using a Packetized Generalized Processor Sharing algorithm to set up a connection pattern of said crossbar switch in each time slot of the cycle time.